Large-scale networked systems are commonplace platforms employed in a variety of settings for running applications and maintaining data for business and operational functions. For instance, a hosting environment such as a data center (e.g., a physical cloud computing infrastructure) may provide a variety of services (e.g., web applications, email services, search engine services, etc.) for a plurality of customers simultaneously. These large-scale networked systems typically include a large number of resources distributed throughout the data center, in which each resource resembles a physical machine or a virtual machine running on a physical host. When the data center hosts multiple tenants (e.g., customer applications), these resources are optimally allocated from the same data center to the different tenants.
When a customer's application is implemented in a hosting environment, the application may be provided by endpoints running on the resources in the hosting environment. As used herein, an endpoint may be a network interface with an address. Because the hosting environment may comprise a private network or the hosted endpoints may otherwise not have public addresses, network address translation (NAT) functionality may be provided to facilitate outgoing connections from the endpoints to entities the private network. A network address translation may be implemented as a distributed system in which multiple NAT devices participate in network address translation while behaving as one single device to the user.